package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/1/17 12:38
 * @description：https://leetcode-cn.com/problems/count-vowels-permutation/
 */
public class 统计元音字母序列的数目 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.countVowelPermutation(144));
    }


    /*
    // 动态规划
    class Solution {
        private int MOD = (int)Math.pow(10, 9) + 7;
        public int countVowelPermutation(int n) {
            long[] count = new long[5];
            Arrays.fill(count, 1);
            for (int i = 1; i < n; i++) {
                long countA = count[0];
                long countE = count[1];
                long countI = count[2];
                long countO = count[3];
                long countU = count[4];
                Arrays.fill(count, 0);
                count[0] = (countE + countI + countU) % MOD;
                count[1] = (countA + countI) % MOD;
                count[2] = (countE + countO) % MOD;
                count[3] = countI;
                count[4] = (countI + countO) % MOD;
            }
            long sum = 0;
            for (long i : count) {
                sum = (i + sum) % MOD;
            }
            return (int) sum;
        }
    }
     */

    class Solution {
        private int MOD = (int) Math.pow(10, 9) + 7;

        public int countVowelPermutation(int n) {
            // 由动态规划解法可以获取矩阵如下
            long[][] factor =
                    {
                            {0, 1, 0, 0, 0},
                            {1, 0, 1, 0, 0},
                            {1, 1, 0, 1, 1},
                            {0, 0, 1, 0, 1},
                            {1, 0, 0, 0, 0}
                    };
            long[][] res = fastPow(factor, n - 1);
            long ans = 0;
            for (int i = 0; i < 5; i++) {
                for (int j = 0; j < 5; j++) {
                    ans = (ans + res[i][j]) % MOD;
                }
            }
            return (int) ans;
        }

        private long[][] fastPow(long[][] factor, int n) {
            int m = factor.length;
            long[][] res = new long[m][m];
            long[][] cur = factor;

            // 将res矩阵初始化为单位矩阵
            for (int i = 0; i < m; i++) {
                res[i][i] = 1;
            }
            
            // 快速幂
            for (int i = n; i != 0; i >>= 1) {
                if ((i % 2) == 1) {
                    res = multiply(cur, res);
                }
                cur = multiply(cur, cur);
            }
            return res;
        }

        private long[][] multiply(long[][] matrixA, long[][] matrixB) {
            int m = matrixA.length;
            int n = matrixB[0].length;
            long[][] res = new long[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < matrixA.length; k++) {
                        res[i][j] = (res[i][j] + matrixA[i][k] * matrixB[k][j]) % MOD;
                    }
                }
            }
            return res;
        }
    }
}
